package code.BinaryTree.二叉树最大宽度;

import struct.Tree;
import struct.TreeNode;

import java.util.HashMap;

class Solution {
	int ans;//3.创建一个存放结果的变量
	HashMap<Integer, Integer> left;//1.创建一个存最左侧位置的map，其它数据结构也可以。

	public static void main(String[] args) {
		TreeNode tree = Tree.constructTree("[1,3,2,5,6,null,9]");
		Solution solution = new Solution();
		int width = solution.widthOfBinaryTree(tree);
		System.out.println(width);
	}

	public int widthOfBinaryTree(TreeNode root) {
		ans = 0;//4.初始化该全局变量
		left = new HashMap();//2.初始化该全局变量。
		dfs(root, 0, 0);
		return ans;//5.返回结果
	}

	public void dfs(TreeNode root, int depth, int pos) {
		if (root == null) return;//6.递归终止条件。
		left.computeIfAbsent(depth, x -> pos);//9.添加最左侧的元素，当第一次走到某一层的时候，此时map里面是空，更新一次位置信息。
		ans = Math.max(ans, pos - left.get(depth) + 1);//10.计算当前结点跟最左侧结点位置的距离，并更新最大值。
		dfs(root.left, depth + 1, 2 * pos);//7.计算左孩子的位置并记录所在层级，在遇到同层级的最左侧元素就可以参与运算得出距离。
		dfs(root.right, depth + 1, 2 * pos + 1);//8.计算左孩子的位置并记录所在层级
	}
}
